package com.ztom.v2;

/**
 * @author ZhangTao
 */
public class Code67FindMinimumInRotatedSortedArray {

    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        int l = 0;
        int r = nums.length - 1;
        // 什么时候写等于: 在循环中能拿到结果
        // 什么时候不写等于: 需要循环至 l == r
        while (l < r) {
            int mid = l + ((r - l) >> 1);
            // 最后一个元素, 第一段都比它大, 第二段都比它小
            if (nums[mid] < nums[nums.length - 1]) {
                // mid 一定在第二段, 最小值在 mid 左边
                // 最小值一定在第二段, 所以不能 -1
                r = mid;
            } else {
                // mid 一定在第一段, 最小值在 mid 右边
                // mid 一定不是最小值, 所以 +1
                l = mid + 1;
            }
        }
        return nums[l];
    }
}
